#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INT_SIZE 100
#define LIST_INCREATMENT 10
#define MAX_SIZE 100
typedef int Status;
typedef int ElemType;

typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;

} DulNode, *DulLinkList;

Status node_init(DulNode *node) // 初始化结构体
{
    node->data = 0;
    node->next = node;  // 构成循环
    node->prior = node; // 构成循环
}

Status head_insert(DulNode *head, ElemType e) // 头插法
{
    DulNode *node = (DulNode *)malloc(sizeof(DulNode)); // 为什么使用DulNOde*而不使用DulLinkList? 答:只有头节点使用DulLinkList(习惯)
    node_init(node);
    node->data = e;         // 先给node存储值
    if (head->next != NULL) // 如果链表不为空
    {
        node->next = head->next;  // 链接后面节点
        node->next->prior = node; // 后面节点的前驱与本节点链接
        head->next = node;        // 链接前面
        node->prior = head;       // 链接前驱
    }
    else // 链表为空
    {
        node->next = head;  // 构成循环
        head->prior = node; // 构成循环
        head->next = node;  // 向后链接head与node
        node->prior = head; // 向前链接head与node
    }
    head->data++; // 记录链表的数据个数
    return OK;
}

Status rear_insert(DulNode *head, ElemType e) // 尾插法在循环链表可以通过不断在头节点前插入实现尾插的效果O(1)
{
    DulNode *node = (DulNode *)malloc(sizeof(DulNode)); // 和头插法一样
    node_init(node);
    node->data = e;          // 先给node存储值
    if (head->prior != NULL) // 如果链表不为空
    {
        head->prior->next = node;  // 头节点的前一个节点指向node
        node->prior = head->prior; // node的前节点等于原来头节点的前节点
        node->next = head;         // node指向头节点
        head->prior = node;        // head的前节点变成node
    }
    else // 链表为空
    {
        node->next = head;  // 构成循环
        head->prior = node; // 构成循环
        head->next = node;  // 向后链接head与node
        node->prior = head; // 向前链接head与node
    }
    head->data++; // 记录链表的数据个数
    return OK;
}

void show_list(DulNode *head) // 展示整个链表
{
    DulNode *p = head; // 记录头节点
    while (p->next != head)
    {
        p = p->next;
        printf("%d ", p->data);
    }
    printf("\n");
}

ElemType get_elem(DulNode *head, int i) // 获取第i个数据,存在返回这个数据,否则返回0
{
    DulNode *p = head; // 这里写p = head.next;下面写int j=1同样可以  [注意:0节点是头节点,不存数据]
    int j = 0;         // 计数器
    while (p->next != head && j < i)
    {
        p = p->next; // 不断向后查找
        j++;         // 计数器记录位置
    }
    if (j==i) // 如果不是到头而退出的
    {
        return p->data;
    }
    else // 到头退出的
    {
        return 0;
    }
}

DulNode *get_elem_pointer_to_delete(DulNode *head, int i, DulNode *pointer) // 获取第i个数据,存在返回一个指向这个结构体的指针,否则指向NULL
{
    DulNode *p = head;
    int j = 0;
    if (!(i >= 1 && i <= head->data)) // 位置不在第一个和lenth之间  这个适用于删除
    {
        return NULL;
    }
    while (p->next != head && j < i)
    {
        p = p->next; // 不断向后查找
        j++;         // 计数器记录位置
    }
    pointer = p;
    return pointer; // 返回指针
}

DulNode *get_elem_pointer_to_insert(DulNode *head, int i, DulNode *pointer) // 获取第i个数据,存在返回一个指向这个结构体的指针,否则指向NULL
{
    DulNode *p = head;
    int j = 0;
    if (!(i >= 1 && i <= head->data + 1)) // 位置不在第一个和lenth之间  这个适用于插入
    {
        return NULL;
    }
    while ((p->next != head && j < i) || (p->next == head && i == head->data + 1)) // 需要特判是不是在最后一个节点后面插入(不知道写的对不对)
    {
        p = p->next; // 不断向后查找
        j++;         // 计数器记录位置
    }
    pointer = p;
    return pointer; // 返回指针
}

Status insert_Element(DulNode *head, int i, ElemType data) // 在第i位置插入数据 (在最后位置插入还没实现)
{
    /*
    课本写法先获取第i位置的指针,如果存在则开始插入。
    课本怎么知道表长的?要在头节点里加入表长吗？
    课本写的含含糊糊的,加上会好写一点
    */
    DulNode *p = NULL;
    p = get_elem_pointer_to_insert(head, i, p); // 拿到要插入位置的指针
    if (p != NULL)
    {
        // printf("%d\n", p->data);
        DulNode *node = (DulNode *)malloc(sizeof(DulNode)); // 建立新空间
        node_init(node);                                    // 初始化链表
        node->data = data;
        // 开始插入
        node->next = p;         // node向后连
        node->prior = p->prior; // node向前连
        p->prior->next = node;  // p曾经的前节点链接node
        p->prior = node;        // p向前连
        head->data++;           // 表长加一
        return OK;
    }
    else
    {
        return ERROR;
    }
}

DulNode *Delete_Element(DulNode *head, int i) // 删除第i个节点,返回这个节点的指针
{
    // 基本思路同插入(删除的范围和插入不同,因为不能删除头节点)
    DulNode *p = NULL;
    // 和插入不同,删除不可以删除头节点,所以需要设置表长(这个地方还没想明白)
    p = get_elem_pointer_to_delete(head, i, p); // 拿到要插入位置的指针
    if (p != NULL)
    {
        p->prior->next = p->next;
        p->next->prior = p->prior;
        head->data--; //
        return p;
    }
    else
    {
        return NULL;
    }
}

int main()
{
    // 创建一个链表头(指针)
    DulLinkList list = (DulLinkList)malloc(sizeof(DulNode));
    node_init(list); // 初始化成一个循环链表

    // for (int i = 1; i < 6; i++)
    // {
    //     // 头插法
    //     head_insert(list, i);
    // }

    for (int i = 1; i < 10; i++)
    {
        // 尾插法
        rear_insert(list, i); // 插入时形成双向链表
    }
    show_list(list); // 展示链表

    // 三个函数:任意位置插入,任意位置删除,获取任意位置的数据
    for (int i = 1; i < 12; i++)
    {
        // 获取第1,2,3位置的数据
        int data = get_elem(list, i); // 获取任意位置的数据
        printf("第%d位置的数据值为:%d\n", i, data);
    }

    // 任意位置插入
    printf("在1,3,5,位置插入(值为10,30,50):\n");
    for (int i = 1; i < 6; i += 2)
    { // 在1,3,5,位置插入(值为10,30,50)
        insert_Element(list, i, i * 10);
    }
    printf("在结尾插入0:\n");
    insert_Element(list, list->data + 1, 0 * 10); // (实现了:这个没有实现(理论应该是在最后位置插入)_
    show_list(list);                              // 展示链表

    // 删除链表第i位置的节点，并返回删除的值
    for (int i = 1; i < 10;)
    {
        DulNode *p = Delete_Element(list, i);
        if (p != NULL)
        {
            printf("删除的值是:%d\n", p->data);
            free(p);
        }
        else
        {
            printf("删除失败,不存在这个位置的节点\n");
            break;
        }
    }
    show_list(list);
}